Motivated by applications to string processing, we introduce variants of theLyndon factorization called inverse Lyndon factorizations. Their factors, namedinverse Lyndon words, are in a class that strictly contains anti-Lyndon words,that is Lyndon words with respect to the inverse lexicographic order. TheLyndon factorization of a nonempty word w is unique but w may have severalinverse Lyndon factorizations. We prove that any nonempty word w admits acanonical inverse Lyndon factorization, named ICFL(w), that maintains the mainproperties of the Lyndon factorization of w: it can be computed in linear time,it is uniquely determined, it preserves a compatibility property for sortingsuffixes. In particular, the compatibility property of ICFL(w) is a consequenceof another result: any factor in ICFL(w) is a concatenation of consecutivefactors of the Lyndon factorization of w with respect to the inverselexicographic order.
展开▼
